// 真题描述：给定一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

// 01 倒数第N个可以转换为链表正数 len - N + 1
// 02 链表的长度可以通过遍历获得

import { ListNode } from './00-utils';
let l1: any = new ListNode(0);
let cur = l1;

for (let index = 0; index < 5; index++) {
  cur.next = new ListNode(index + 1);
  cur = cur.next;
}

// 获取列表长度
function getListNodeLen(l1: any) {
  if (!l1) return 0;
  let count = 0;
  while (l1) {
    count++;
    l1 = l1.next;
  }
  return count;
}

// 删除第N个链表结点
function delNthListNode(l1: any, n: number) {
  const len = getListNodeLen(l1);
  let cur = l1;
  let count = 1;
  while (cur) {
    if (count == n - 1) {
      cur.next = cur.next.next;
      return l1;
    }
    cur = cur.next;
    count++;
  }
}
// 上面的是常规的做法

// 使用快慢指针加dummy指针的方法实现

const removeNthFromEnd = function (head: ListNode, n: number) {
  // 初始化dummy节点
  const dummy: ListNode = new ListNode();
  // dummy指向头结点
  dummy.next = head;
  // 初始化快慢指针
  let fast: ListNode = dummy;
  let slow: ListNode = dummy;
  // 快指针门头走n步骤
  while (n != 0) {
    if (fast?.next) fast = fast.next;
    n--;
  }
  // 然后快慢指针一起走
  while (fast.next) {
    if (slow.next) slow = slow.next;
    if (fast.next) fast = fast.next;
  }
  // 当上面循环fast.next 为空的时候,slow指针正好在倒数第n项
  // 慢指针删除自己的后继结点
  slow.next = slow.next?.next || null;
};
